# -*- encoding: utf-8 -*-
'''
Filename         :25_reverseKGroup.py
Description      :
Time             :2022/08/19 14:35:57
Author           :daiyizheng
Email            :387942239@qq.com
Version          :1.0
'''

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    # 思路，先反转头和尾
    def reverseKGroup(self, 
                      head: Optional[ListNode], 
                      k: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        p = dummy
        while True:
            count = k
            stack = []
            tmp = head

            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count-=1
            # 注意,目前tmp所在k+1位置
            # 说明剩下的链表不够k个,跳出循环
            if count:
                p.next = head
                break

            # 反转操作
            while  stack:
                p.next = stack.pop()
                p = p.next
            ## 将设剩下的链接起来
            p.next = tmp
            head = tmp
        return dummy.next